Although evolutionary computing has roots as far back as the 1950s, genetic algorithms (hereinafter referred to by the initials GA) were introduced in 1975 by John Holland as a method for finding an optimum or near optimum solution to complicated problems. As noted by another researcher, Grefenstette, the GA is a useful method for finding optimum solutions to the Traveling Salesman Problem, a classic and well-known computationally intractable problem.
With reference now to FIG. 1, there is illustrated therein a conceptual model of evolution in a genetic algorithm and how a solution to a problem evolves in processing the GA, generally designated by the reference numeral 100. As is understood in this art, in a genetic algorithm, an emulated chromosomal data structure is initially designed to represent a candidate or trial solution. A number of n-bit chromosomes of that data structure are then randomly generated and are registered in groups or populations of solutions. Parent chromosomes are selected from this population of generated chromosomes according to a given algorithm, e.g., selected chromosomes 105 and 110 in FIG. 1. Each generated chromosome is assigned a unique problem-specific fitness which may or may not differ from other chromosomes in the population, identifying the solution quality of the chromosome. The problem-specific fitness is expressed by a fitness value, as is known in the art. In a true evolutionary, survival of the fittest manner, particular chromosomes are selected from the population of chromosomes in proportion to their fitness values with more-fit chromosomes having a higher probability of being selected.
As further illustrated in FIG. 1, when a pair of parent chromosomes, e.g., chromosomes 105 and 110, are selected from the population, the parent chromosomes are combined using a probabilistically generated cut point, designated by the reference numeral 120. In the case of having no cutpoint generated, either of the parent chromosomes is simply copied to provide a new chromosome as a child chromosome. Thus, a child chromosome is created and outputted. The child chromosome, therefore, contains portions of each parent or the whole portion of a parent, e.g., a child chromosome 125 contains portion 105A of parent chromosome 105 and portion 110B of parent chromosome 110, as illustrated in FIG. 1. The child chromosome may then be mutated in a controlled manner, preferably having a low probability. In the evolutionary example illustrated in FIG. 1, the mutation is performed through inversion of a bit 130 in the child chromosome 125, e.g., 0 to 1 or 1 to 0. A mutated child chromosome 125′ is then evaluated to be assigned its fitness value. An evaluated child chromosome along with its fitness value is then stored as a member of the next generation in the population, perhaps replacing one or both of the associated parent chromosomes 105 and 110.
After repeated iteration of this evolutionary process, the general fitness of chromosomes in the population improves to the optimal solution. Thus, a solution to the problem emerges in the population, and is acquired with highly-fit chromosomes concentrated in the population.
In a conventional approach, a GA is emulated by software and the algorithm used for computing the fitness of a GA-based candidate solution to the combinatorial problem is also emulated by software. Due to such a software-based emulation on conventional computers, however, the execution speed of the algorithm for finding an optimum solution to the combinatorial problem is extremely slow. Indeed, a major drawback of conventional genetic algorithm machines is the slow execution speed of a GA when emulated by software on conventional, general-purpose computers.
A hardware-based implementation of a GA has been devised for offsetting the drawback but only with a limited success in its execution speed. For example, U.S. Pat. No. 5,970,487 to Shackleford, et al. solved some of the drawbacks and disadvantages of prior art techniques, particularly speed of operation, by the utilization of a hardware-based framework for accelerated used of genetic algorithms. The advantages and usages of the Shackleford et al. invention, Shackleford being the sole inventor in the instant application, are fully described in U.S. Pat. No. 5,970,487, which is incorporated by reference herein.
The Shackleford et al. invention as described is an efficient problem-solving machine that may evolve solutions to many different problems. A common problem that is generally solved using a genetic algorithm is a combinatorial problem, also called a routing or ordering problem. A particularly intractable combinatorial problem is a so-called non-deterministic polynomial hard (NP-hard) problem, which may be solved through a resource selection from among many resources, by an applied form of a GA, minimizing the hardware architecture, of a logic circuit, for example, and generating a resultant optimum solution.
An example of an NP-hard combinatorial problem is the aforementioned Traveling Salesman Problem (or TSP), as is known in the art, which can be used to model many combinatorial, routing and ordering problems. The TSP seeks to find the shortest route between n cities, and while any solution which contains all n cities once and only once is valid, some solutions are better than others. A solution to this problem describes the order of travel between cities, which determines the distance of the route traveled, so the order of travel between cities having the shortest route is the best solution. As is well understood in the mathematical and computer algorithm arts, the TSP is an NP-hard combinatorial problem with n! potential solutions and (n−1)! unique solutions.
With reference now to FIG. 2, there is illustrated an example solution and its fitness for an 8-city Traveling Salesman Problem. The solution to the TSP is in the form of the order traveled and yields a fitness value calculated from a distance Dx,y of each new city from the last. In this example, the possible solution to the 8 city TSP {0, 4, 2, 7, 5, 6, 3, 1} corresponds to the fitness value DTotal=D0,4+D4,2+D2,7+D7,5+D5,6+D6,3+D3,1+D1,0, as in understood to those skilled in the art. As illustrated in FIG. 2, other routes are possible and, alternatively, a possible solution can include information of order traveled from any city to any other, with no repetition of cities. For simplicity, not all possible routes are shown in FIG. 2.
Because of the large number of possible solutions to a TSP, e.g., a 32-city TSP has over 2.5*1035 solutions, heuristic and non-deterministic solving methods must be used to solve this type of problem. The TSP can be solved, therefore, through an optimal solution-finding approach that aims at attaining an optimal or near optimal solution through a screening process of candidate or trial solutions created through a GA, based upon a fitness evaluation of the candidate solutions. In this approach, more-fit candidate solutions are selected with less-fit candidate solutions screened out to concentrate highly-fit solutions or chromosomes and in the end to reach an optimal or near optimal solution.
The Shackleford et al. invention as described hereinabove achieves a significant increase in execution speed in its hardware implementation. The Shackleford et al. invention is a general purpose GA machine that can solve any problem by using the appropriate chromosome generation template and fitness function circuit. However, general purpose machines are always less efficient than task-specific dedicated machines, and the GA machine is no exception.
There is, therefore, a present need to provide a problem-specific, combinatorial-type fitness function circuit which performs a high speed fitness evaluation of candidate solutions generated through a GA. What is needed is, accordingly, an invention to provide a hardware-based fitness function circuit which accelerates the execution speed of a GA. What is needed is an invention to provide a hardware-based fitness function circuit.
The present invention describes a method to provide a high-speed, hardware-based fitness function that will match the performance of the hardware-based implementation of the GA.
It is, accordingly, an aspect of the present invention to provide a problem-specific, combinatorial-type fitness function circuit which performs a high speed fitness evaluation of candidate solutions generated through a GA.
It is another aspect of the present invention to provide a fitness function circuit which accelerates the execution speed of a GA.
It is a further aspect of the present invention to provide a hardware-based fitness function circuit.